package demo1;

import java.util.*;

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        //TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        //G.right = H;

        return A;
    }
    //二叉树创建字符串
    public String tree2str(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        treeToString(root,sb);
        return sb.toString();
    }
    public void treeToString(TreeNode t, StringBuilder sb) {
        if (t == null) {
            return;
        }
        sb.append(t.val);
        if (t.left != null) {
            sb.append("(");
            treeToString(t.left,sb);
            sb.append(")");
        } else {
            if (t.right == null) {
                return;
            } else {
                sb.append("()");
            }
        }
        if (t.right == null) {
            return;
        } else {
            sb.append("(");
            treeToString(t.right,sb);
            sb.append(")");
        }
    }

    //判断一个树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            if (queue.peek() == null) {
                break;
            }
            TreeNode cur = queue.poll();
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }
    //非递归的前序遍历
    public void preOrderNor(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        System.out.print(root.val + " ");
        while(!stack.empty()) {
            if (root.left == null) {
                while (!stack.empty()) {
                    root = stack.pop();
                    root = root.right;
                    if (root != null) {
                        stack.push(root);
                        System.out.print(root.val + " ");
                        break;
                    }
                }
            } else {
                stack.push(root.left);
                root = root.left;
                System.out.print(root.val + " ");
            }
        }
    }
    //非递归中序遍历
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.empty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }
    //二叉树非递归后序遍历
    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (root != null || !stack.empty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.peek().right;
                if (root == null || root == prev) {
                    TreeNode del = stack.pop();
                    list.add(del.val);
                    prev = del;
                    root = null;
                }
//                if (!flag) {
//                    list.add(stack.pop().val);
//                    root = stack.pop().right;
//                    flag = true;
//                } else {
//                    root = stack.peek().right;
//                    flag = false;
//                }
            }
        }
        return list;
    }
}
